package dp;

public class _03_746_使用最小花费爬楼梯 {
	static int N = 1010;
	static int dp[] = new int[N];
    public static int minCostClimbingStairs(int[] cost) {
    	// 每次只能爬一个台阶或者两个台阶
    	// 设爬到当前台阶，前一个台阶 以及 前第二个台阶 哪个到当前台阶费用最低
    	// 前一二个台阶的值是之前爬到该台阶的最低费用，那么要爬到当前台阶，就需要分别加上他们的值，再取两者最小值
    	for(int i = 2; i <= cost.length; i++) {
    		dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
    	}
    	
    	return dp[cost.length];
    }
    
    public static void main(String[] args) {
    	int cost[] = {1,100,1,1,1,100,1,1,100,1};
		System.out.println(minCostClimbingStairs(cost));
	}
}
